// standard headers
#include <istream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <stdexcept>
#include <map>
#include <cstdlib>

// boost headers
#include <boost/format.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/filesystem/path.hpp>

// components headers
#include <tree.h>
#include <tree_ops.h>
#include <portable_timer.h>
#include <progress_indicator.h>
#include <print_error.h>
#define DEBUG_LEVEL 6
#include <debug_func.h>





using boost::format;
using boost::lexical_cast;
using boost::filesystem::path;
using std::vector;
using std::ostringstream;

using std::string;
using std::fill;
using std::ofstream;
using std::cout;
using std::cin;
using std::cerr;
using std::ifstream;
using std::map;
using std::pair;
using std::istream;
using std::max;
using std::min;
using namespace bcpp_matrix;
using namespace bcpp_tree_ops;


struct do_reroot
{
	vector<bcpp_tree::t_edge>	branches;
	std::ostream&					os;
	bcpp_tree::t_tree&				tree;
	op_print_tree_elaborate&		print_tree_elaborate;
	op_dump_tree_data 				dump_tree;
	do_reroot(	bcpp_tree::t_tree&				tree_,
				std::ostream& 					os_,
				op_print_tree_elaborate&		print_tree_elaborate_):
			os(os_),
			tree(tree_),
			print_tree_elaborate(print_tree_elaborate_),
			dump_tree(tree_, os_)
	{}
	void recurse(bcpp_tree::t_node* node, unsigned);
};

void do_reroot::recurse(bcpp_tree::t_node* node, unsigned ignore)
{                                                  
	static unsigned level = 0;                    ;
	debug_func_cerr(5);
	unsigned cnt_children = node->get_children_count();
	// is leaf
	if (!cnt_children)
	{
		return;
	}

	++level;
	// handle all  child with grandchildren
	for (unsigned i = 0; i < cnt_children; ++i)
	{
		//if (i == ignore)
		//	continue;
		if (node->get_child(i)->get_children_count())
		{
			float reroot_a, reroot_b, reroot_c;
			tree.reroot(i, 0, reroot_a, reroot_b, reroot_c);
			os	<< "\nReroot 0 at " << i << "\n";
			//os	<< "New children of root = "
			//		<< tree.get_root()->get_child(0)->get_name() << " and "
			//		<< tree.get_root()->get_child(1)->get_name() << "\n";
			os << tree << "\n";
			dump_tree.dump();
			branches.push_back(bcpp_tree::t_edge(tree.get_root()->get_child(0), tree.get_root()->get_child(1)));
			//print_tree_elaborate.print();
			recurse(node->get_child(i),0);
			tree.undo_reroot(i, 0, reroot_a, reroot_b, reroot_c);
			os << "Undone\n";
			os << tree << "\n";

			tree.reroot(i, 1, reroot_a, reroot_b, reroot_c);
			os	<< "\nReroot 1 at " << i << "\n";
			//os	<< "New children of root = "
			//		<< tree.get_root()->get_child(0)->get_name() << " and "
			//		<< tree.get_root()->get_child(1)->get_name() << "\n";
			os << tree << "\n";
			dump_tree.dump();
			branches.push_back(bcpp_tree::t_edge(tree.get_root()->get_child(0), tree.get_root()->get_child(1)));
			//print_tree_elaborate.print();
			recurse(node->get_child(i),1);
			tree.undo_reroot(i, 1, reroot_a, reroot_b, reroot_c);
			os << "Undone\n";
			os << tree << "\n";
		}
	}
	--level;
}







//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	main

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

int main (int argc, char *argv[])
{
	// we use cout to print progress so flush per call
//	cout.setf(std::ios_base::unitbuf);

	std::ios::sync_with_stdio(false);

	try
	{
		// read species tree
		unsigned line_cnt = 0;
		bcpp_tree::t_tree initial_tree;
			read_tree_from_stream(cin, initial_tree, line_cnt);
		if (!cin)
			throw std::runtime_error("No tree supplied.");
	
		cerr << "\tCalculating branch lengths...\n";
		// calculate branch lengths
		bcpp_tree_ops::do_calculate_branch_lengths branch_lengths(initial_tree);
	
		// set node type to none
		std::vector<eNODETYPE>	node_types(initial_tree.get_node_count(), eNONE);
	
	
		// print
		op_print_tree_elaborate print_tree_elaborate
									(initial_tree,
									cout,
									branch_lengths.lengths_to_leaves,
									branch_lengths.lengths_to_root,
									node_types,
									3	// precision
									);
		cout << "Original tree:\n";
		print_tree_elaborate.print();
		cout << initial_tree << "\n";
		do_reroot reroot(initial_tree, cout, print_tree_elaborate);
		cout << "Rerooting recursively...\n";
		reroot.recurse(initial_tree.get_root(),0);
		reroot.recurse(initial_tree.get_root(),1);
		cerr << "Rerooting randomly...\n";
		cout << "Rerooting randomly...\n";
		for (unsigned i = 0; i < 150; ++i)
		{
			unsigned index = rand() % reroot.branches.size();
			initial_tree.reroot(reroot.branches[index].parent, reroot.branches[index].child);
			print_tree_elaborate.print();
			initial_tree.assert_consistency();
		}
	
	
		cerr << "\n\tAll finished!!\n\n";
	}
	catch (std::exception& e)
	{
		std_print_error(cerr,  e.what());
		return 1;
	}

	return 0;
}


